home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ASME's Mechanical Engine…ing Toolkit 1997 December
/
ASME's Mechanical Engineering Toolkit 1997 December.iso
/
ai
/
prlg195b.lzh
/
PUZZLES.LZH
/
MISCAN.PRO
< prev
next >
Wrap
Text File
|
1986-07-20
|
7KB
|
168 lines
/* Missionary-cannibal-boat problem
Three missionaries and three cannibals meet at the south bank of
a river. A boat, capable of holding one rower and one passenger,
is tied to the bank. All persons wish to cross to the other side
(the north bank) of the river.
A complicating factor is that, should the cannibals outnumber the
missionaries on either bank or in the boat, the cannibals will
kill and eat the missionaries. This is a situation that the
missionaries, not all that sure of their eternal deliverance,
fervently wish to avoid.
The code below generates a solution to the problem.
The problem solving process is initiated by the statement
solvex(statex(0,0,3,3,south),[]).
where the predicate statex is described below and the []
represents the initially empty solution list of states.
The predicate statex gives the circumstances after each 'move' of
the problem. It is defined as:
statex(#missionaries on north shore,
#cannibals on north shore,
#missionaries on south shore,
#cannibals on south shore,
shore on which boat resides)
The other predicates used in this solution of the problem are:
predicate description
********* *******************************************
movex generates a new move from the current state
goodx tests a state to see if it is an 'allowed'
state, i.e. determines that the number of
missionaries on each shore is greater than
the number of cannibals on that shore.
member tests a state to see if it has been used
before, i.e., prevents a logical loop.
prt prints the final list of the states traversed
to reach the problem solution.
\*
The following predicate must be first. */
solvex(statex(3,3,0,0,north),Print_list) :- prt(Print_list),!.
/*
.PA
This predicate accepts the initial state and starts the
problem solving process. */
solvex(statex(0,0,3,3,south),[]) :-
movex(statex(0,0,3,3,south),statex(Mmn,Mcn,Mms,Mcs,north)),
goodx(statex(Mmn,Mcn,Mms,Mcs,north)),
solvex(statex(Mmn,Mcn,Mms,Mcs,north),
[[Mmn,Mcn,Mms,Mcs,north],[0,0,3,3,south]]).
/* The predicate below does most of the work - it accepts the
current state and generates a new move in the puzzle. */
solvex(statex(Missionary_north, Cannibal_north,
Missionary_south, Cannibal_south, Shore),
List) :-
movex(statex(Missionary_north, Cannibal_north,
Missionary_south, Cannibal_south, Shore),
statex(Mmn,Mcn,Mms,Mcs,Sh)),
goodx(statex(Mmn,Mcn,Mms,Mcs,Sh)),
not(member([Mmn,Mcn,Mms,Mcs,Sh],List)),
solvex(statex(Mmn,Mcn,Mms,Mcs,Sh),
[[Mmn,Mcn,Mms,Mcs,Sh]|List]).
/* The good states (for the missionaries) are given below */
goodx(statex(Mmn,Mcn,Mms,Mcs,_)) :- (Mmn >= Mcn), (Mms >= Mcs),
(Mmn >= 0), (Mms >= 0),
(Mcn >= 0), (Mcs >= 0).
goodx(statex(Mmn,Mcn,Mms,Mcs,_)) :- (Mmn = 0), (Mms >= 0),
(Mcs >= 0), (Mcn >= 0).
goodx(statex(Mmn,Mcn,Mms,Mcs,_)) :- (Mms = 0), (Mmn >= 0),
(Mcs >= 0), (Mcn >= 0).
/*
The possible moves are given below. Start with
north to south moves of missionaries. */
movex(statex(Mmn,Mcn,Mms,Mcs,north),
statex(Nmn,Ncn,Nms,Ncs,south)) :-
Nmn is Mmn - 2, Nms is Mms + 2,
Ncn is Mcn, Ncs is Mcs.
movex(statex(Mmn,Mcn,Mms,Mcs,north),
statex(Nmn,Ncn,Nms,Ncs,south)) :-
Nmn is Mmn - 1, Nms is Mms + 1,
Ncn is Mcn, Ncs is Mcs.
/*
.PA
Now define the north to south moves of cannibals. */
movex(statex(Mmn,Mcn,Mms,Mcs,north),
statex(Nmn,Ncn,Nms,Ncs,south)) :-
Ncn is Mcn - 2, Ncs is Mcs + 2,
Nmn is Mmn, Nms is Mms.
movex(statex(Mmn,Mcn,Mms,Mcs,north),
statex(Nmn,Ncn,Nms,Ncs,south)) :-
Ncn is Mcn - 1, Ncs is Mcs + 1,
Nmn is Mmn, Nms is Mms.
/* Now define north to south moves via an integrated boat.*/
movex(statex(Mmn,Mcn,Mms,Mcs,north),
statex(Nmn,Ncn,Nms,Ncs,south)) :-
Nmn is Mmn - 1, Nms is Mms + 1,
Ncn is Mcn - 1, Ncs is Mcs + 1.
/* Now define all the south to north moves. Start with
south to north moves of missionaries. */
movex(statex(Mmn,Mcn,Mms,Mcs,south),
statex(Nmn,Ncn,Nms,Ncs,north)) :-
Nmn is Mmn + 2, Nms is Mms - 2,
Ncn is Mcn, Ncs is Mcs.
movex(statex(Mmn,Mcn,Mms,Mcs,south),
statex(Nmn,Ncn,Nms,Ncs,north)) :-
Nmn is Mmn + 1, Nms is Mms - 1,
Ncn is Mcn, Ncs is Mcs.
/*
Now define the south to north moves of cannibals. */
movex(statex(Mmn,Mcn,Mms,Mcs,south),
statex(Nmn,Ncn,Nms,Ncs,north)) :-
Ncn is Mcn + 2, Ncs is Mcs - 2,
Nmn is Mmn, Nms is Mms.
movex(statex(Mmn,Mcn,Mms,Mcs,south),
statex(Nmn,Ncn,Nms,Ncs,north)) :-
Ncn is Mcn + 1, Ncs is Mcs - 1,
Nms is Mms, Nmn is Mmn.
/*
.PA
Now define south to north moves via an integrated boat.*/
movex(statex(Mmn,Mcn,Mms,Mcs,south),
statex(Nmn,Ncn,Nms,Ncs,north)) :-
Nmn is Mmn + 1, Nms is Mms - 1,
Ncn is Mcn + 1, Ncs is Mcs - 1.
/* The member predicate definition */
member(X,[X|_]).
member(X,[_|L]) :- member(X,L).
/* Predicate to print the final result */
prt([]) :- nl.
prt([X|L]) :- write(X),nl,prt(L).
/* End of predicate definition */